Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Hallo allerseits. Die Reihen sind hier etwas ausgedünnt. Ich vermute, alle sind am Kalab programmieren.

Wir haben übrigens nachgedacht und wir sind zu dem Schluss gekommen, dass wir es nicht verschieben wollen.

Das ist ein offenes Turnier und man kann das ja auch im nächsten Jahr darunter mischen und gucken, wie man abschneidet.

Und den Frischlingen zeigt, was eine Harke ist.

Die Gefahr dabei ist natürlich, dass die Frischlingen einem selber zeigen, was eine Harke ist.

Gut, wir haben uns gestern mit dem neuen Thema Constraint Propagation beschäftigt.

Constraint Propagation ist wieder so eine Sache, wo es keine vernünftige deutsche Übersetzung gibt.

Im Wesentlichen geht es darum, die Constraints irgendwie weiter zu verteilen.

Das ist so hier das, was wir gestern gemacht haben.

Wir sind angestiegen von der Suche auf Constraints selber hin dazu, uns die Problembeschreibungen wirklich anzugucken und auf die Transaktionen zu überführen.

Also statt Zuständen Probleme zu transformieren. Und das natürlich mit Suche mischen.

Suche ist immer unser Fallback.

Aber manchmal können wir eben Inferenz machen und hier ist die Idee, dass wenn wir die Problembeschreibung angucken,

die momentane Problembeschreibung, und dass wir gewisse Erkenntnisse finden, neue Informationen, die wir wiederum in die Problembeschreibung reinschreiben können.

Das ist die Idee. Und sehr häufig ist es so, dass uns die neuen verbesserten Problembeschreibungen bessere Suchsysteme geben.

So viel besseres Suchverhalten geben, dass es sich lohnt, in bessere Problembeschreibungen zu investieren.

Das haben wir uns gestern angeguckt.

Und im Wesentlichen haben wir uns zwei Sachen angeguckt.

Wir haben uns Forward Checking als eine sehr einfache Inferenzmethode angeguckt.

Und wir haben uns dann Art-Consistency, also Pfadkonsistenzmethode, angeguckt als eine etwas leistungsfähigere Methode.

Und Pfadkonsistenz ist eigentlich so in jedem, ist der Motor von allen State-of-the-Art-Systemen, die halt eben wirklich mit den Zuständen arbeiten.

Es gibt auch noch andere Möglichkeiten, wie man Constraint-Satisfaction machen kann.

Aber das klassische Constraint-Satisfaction läuft über Art-Consistency.

Die anderen Sachen, die wir uns heute noch angucken werden, sind so hier Dekompositionsverfahren.

Das heißt, wir haben ein Problem, wir gucken uns das scharf an und sehen, dass wir daraus typischerweise mehrere kleinere machen.

Oder einen schweren Teil und einen leichten Teil, den man dann leicht erschlagen kann und solche Dinge.

Inferenz als ein Verfahren, wie man Problembeschreibungen in andere Problembeschreibungen überführt, ohne dass sich die Lösungsmengen ändern.

Das ist das Wichtige daran.

Problem nehmen, irgendein anderes Problem daraus machen, kann auch Spaß machen, ist aber nicht das, was wir hier wollen.

Was wir hier wollen, ist, dass wir die Lösungsmengen gleich lassen, nur ein Problem erstellen, was sich besser verhält.

Am liebsten in eine Form bringen, von der man die Lösung sofort ablesen kann.

Wenn man irgendwie etwas von der Bauart hat, V hat eine Eilelemente, die man domänet, dann weiß ich genau, was die Lösung für V sein muss.

Wir hatten uns ein paar Beispiele für Äquivalenz angeguckt.

Wir waren dann auf diese Idee der Verschärfungen gekommen.

Da gab es eine Diskussion, ob diese Inklusion vielleicht verkehrt rum sei.

Ich habe mich dazu breitschlagen lassen, dass sie wahrscheinlich verkehrt rum ist.

Ich habe es mir dann noch einmal zu Hause in Ruhe angeguckt und sie ist nicht verkehrt rum, sondern es war richtig.

Die Idee dabei ist, wenn man Verschärfungen hat, dass die Domänen bzw. die Constraints als Mengen klein werden.

Was man sich vorstellen muss, ist, dass man sie verschärfen kann, wenn man sie kleiner macht.

Im Extremfall ist der Constraint leer.

Das heißt, er hat kein einziges Paar, das heißt, ich kann ihn gar nicht erfüllen.

Im anderen Extremfall ist es das ganze kathesische Produkt.

Alle Paare. Der ist so groß, dass man ihn auch weglassen kann, weil man ihn gar nicht anders kann als erfüllen.

Egal was man macht, der macht überhaupt keine Beschränkung.

Das heißt, hier ist diese Verschärfung C' als eine Teilmenge von Cuv die richtige Sache.

Okay?

Gut. Und auch da hatten wir uns einige Beispiele angeguckt.

Als unser neuer Allgemeiner Algorithmus hatten wir uns diesen Backtracking with Inference angeguckt.

Das ist also ein Backtrack-Algorithmus, der, wenn unsere Inferenzprozeduren nichts am Problem ändern, das kann ja sein,